IEEE INFOCOM 2021

Session F-3

AoI

Conference

10:00 AM — 11:30 AM EDT

Local

May 12 Wed, 9:00 AM — 10:30 AM CDT

Age of Information in Random Access Networks with Stochastic Arrivals

Igor Kadota (Columbia University, USA); Eytan Modiano (MIT, USA)

1

We consider a Random Access network with a number of nodes transmitting time-sensitive information to a wireless base station. Packets are generated according to a stochastic process and nodes employ either Slotted-ALOHA or Carrier-Sense Multiple Access (CSMA) to transmit these packets. A packet collision occurs when two or more nodes transmit simultaneously and a successful packet transmission occurs when a node transmits without interference. The goal is to optimize the Random Access mechanism in terms of information freshness, which is captured by the Age of Information (AoI) metric.

In this paper, we propose a framework to analyze and optimize the average AoI in Random Access networks with stochastic packet generation. In particular, we develop a discrete-time model, derive an approximate expression for the average AoI in the network, and then use this expression to optimize the Random Access mechanism. Furthermore, we implement the optimized Random Access mechanism in a Software Defined Radio testbed and compare the AoI measurements with analytical and numerical results in order to validate our framework. Our approach allows us to evaluate the combined impact of the packet generation rate, transmission probability, and size of the network on the AoI performance.

Analyzing Age of Information in Multiaccess Networks by Fluid Limits

Zhiyuan Jiang (Shanghai University, China)

1

In this paper, we adopt the fluid limits to analyze Age of Information (AoI) in a wireless multiaccess network with many users. We consider the case wherein users have heterogeneous i.i.d. channel conditions and the statuses are generate-at-will. Convergence of the AoI occupancy measure to the fluid limit, represented by a Partial Derivative Equation (PDE), is proved within an approximation error inversely proportional to the number of users. Global convergence to the equilibrium of the PDE, i.e., stationary AoI distribution, is also proved. Based on this framework, it is shown that an existing AoI lower bound in the literature is in fact asymptotically tight, and a simple threshold policy, with the thresholds explicitly derived, achieves the optimum asymptotically. The proposed threshold-based policy is also much easier to decentralize than the widely-known index-based policies which require comparing user indices. To showcase the usability of the framework, we also use it to analyze the average non-linear AoI functions (with power and logarithm forms) in wireless networks. Again, explicit optimal threshold-based policies are derived, and average age functions proven. Simulation results show that even when the number of users is limited, e.g., 10, the proposed policy and analysis are still effective.

Minimizing the Sum of Age of Information and Transmission Cost under Stochastic Arrival Model

Kumar Saurav (Tata Institute of Fundamental Research, India); Rahul Vaze (TIFR Mumbai, India)

0

We consider a node-monitor pair, where updates are generated stochastically (according to a known distribution) at the node that it wishes to send to the monitor. The node is assumed to incur a fixed cost for each transmission, and the objective of the node is to find the update instants so as to minimize a linear combination of AoI of information and average transmission cost. First, we consider the Poisson arrivals case, where updates have an exponential inter-arrival time for which we derive an explicit optimal online policy. Next, for arbitrary distributions of inter-arrival time of updates, we propose a simple randomized algorithm that transmits any newly arrived update with a fixed probability (that depends on the distribution) or never transmits that update. The competitive ratio of the proposed algorithm is shown to be a function of the variance and the mean of the inter-arrival time distribution. For some of the commonly considered distributions such as exponential, uniform, and Rayleigh, the competitive ratio bound is shown to be 2.

Real-time sampling and estimation on random access channels: Age of Information and Beyond

Xingran Chen, Xinyu Liao and Shirin Saeedi Bidokhti (University of Pennsylvania, USA)

1

Real-time sampling and estimation of autoregressive Markov processes is considered in random access channels. Two classes of policies are studied: (i) oblivious policies in which decision making is independent of the source realizations, and (ii) non-oblivious policies in which sources are observed causally for decision making. In the first class, minimizing the expected time-average estimation error is equivalent to minimizing the expected age of information (AoI). Lower and upper bounds are provided for the achievable estimation error in this class and age-based threshold policies are shown to provide a two-fold improvement compared to the state-of-the-art. In the second class, an error-based threshold policy is proposed: a transmitter becomes active when its error exceeds a threshold in which case it transmits probabilistically following slotted ALOHA. A closed-form expression is derived for the estimation error as a function of the peak age, the transmission delay, a term which we call the silence delay, as well as the source realization. It is analyzed approximately by considering the underlying source as a discretized Wiener process. The proposed threshold policy provides a three-fold improvement compared to oblivious policies and its performance is close to that of centralized greedy scheduling.

Session Chair

I-Hong Hou (Texas A&M University)

Session F-4

Scheduling 1

Conference

12:00 PM — 1:30 PM EDT

Local

May 12 Wed, 11:00 AM — 12:30 PM CDT

Motion-Prediction-based Wireless Scheduling for Multi-User Panoramic Video Streaming

Jiangong Chen, Xudong Qin and Guangyu Zhu (University of Rhode Island, USA); Bo Ji (Virginia Tech, USA); Bin Li (University of Rhode Island, USA)

1

Multi-user panoramic video streaming demands 4 ∼ 6× bandwidth of a regular video with the same resolution, which poses a significant challenge on the wireless scheduling design to achieve desired performance. On the other hand, recent studies reveal that one can effectively predict the user's Field-of-View (FoV) and thus simply deliver the corresponding portion instead of the entire scenes. Motivated by this important fact, we aim to employ autoregressive process for motion prediction and analytically characterize the user's successful viewing probability as a function of the delivered portion. Then, we consider the problem of wireless scheduling design with the goal of maximizing application-level throughput (i.e., average rate for successfully viewing the desired content) and service regularity performance (i.e., how often each user gets successful views) subject to the minimum required service rate and wireless interference constraints. As such, we incorporate users' successful viewing probabilities into our scheduling design and develop a scheduling algorithm that not only asymptotically achieves the optimal application-level throughput but also provides service regularity guarantees. Finally, we perform simulations to demonstrate the efficiency of our proposed algorithm using a real dataset of users' head motion.

Optimal Wireless Scheduling for Remote Sensing through Brownian Approximation

Daojing Guo (Texas A&M University, USA); Ping-Chun Hsieh (National Chiao Tung University, Taiwan); I-Hong Hou (Texas A&M University, USA)

0

This paper studies a remote sensing system where multiple wireless sensors generate possibly noisy information updates of various surveillance fields and delivering these updates to a control center over a wireless network. The control center needs a sufficient number of recently generated information updates to have an accurate estimate of the current system status, which is critical for the control center to make appropriate control decisions. The goal of this work is then to design the optimal policy for scheduling the transmissions of information updates. Through Brownian approximation, we demonstrate that the control center's ability to make accurate real-time estimates depends on the averages and temporal variances of the delivery processes. We then formulate a constrained optimization problem to find the optimal means and variances. We also develop a simple online scheduling policy that employs the optimal means and variances to achieve the optimal system-wide performance. Simulation results show that our scheduling policy enjoys fast convergence speed and better performance when compared to other state-of-the-art policies.

Randomized Scheduling of Real-Time Traffic in Wireless Networks Over Fading Channels

Christos Tsanikidis and Javad Ghaderi (Columbia University, USA)

1

Despite the rich literature on scheduling algorithms for wireless networks, algorithms that can provide deadline guarantees on packet delivery for general traffic and interference models are very limited. In this paper, we study the problem of scheduling real-time traffic under a conflict-graph interference model with unreliable links due to channel fading. Packets that are not successfully delivered within their deadlines are of no value. We consider traffic (packet arrival and deadline) and fading (link reliability) processes that evolve as an unknown finite-state Markov chain. The performance metric is efficiency ratio which is the fraction of packets of each link which are delivered within their deadlines compared to that under the optimal (unknown) policy. We first show a conversion result that shows classical non-real-time scheduling algorithms can be ported to the real-time setting and yield a constant efficiency ratio, in particular, Max-Weight Scheduling (MWS) yields an efficiency ratio of 1/2. We then propose randomized algorithms that achieve efficiency ratios strictly higher than 1/2, by carefully randomizing over the maximal schedules. We further propose low-complexity and myopic distributed randomized algorithms, and characterize their efficiency ratio. Simulation results are presented that verify that randomized algorithms outperform classical algorithms such as MWS and GMS.

Rate Region of Scheduling a Wireless Network with Discrete Propagation Delays

Jun Ma, Yanxiao Liu and Shenghao Yang (The Chinese University of Hong Kong, Shenzhen, China)

1

We study the link scheduling problem of wireless networks where signal propagation delays are multiples of certain time interval. The problem can be modeled as a character of the independent sets of periodic graphs, which have infinitely many vertices. We show that the rate region of scheduling a network can be achieved using collision-free, periodic schedules, and derive a graphical approach to explicitly characterize the rate region. In particular, a collision-free schedule can be equivalent to a path in a graph called the scheduling graph induced by the network collision profile and the propagation delays, and hence the rate region is equal to the convex hull of the rate vectors associated with the cycles of the scheduling graph, which have bounded length. With the maximal independent set problem as a special case, calculating the whole rate region is NP hard and also hard to approximate. By exploring a partial order on the paths, we derive an algorithm to calculate a subset of the rate region more efficiently. Our results are also of independent interest for periodic graphs.

Session Chair

Haipeng Dai (Nanjing University, China)

Session F-5

Scheduling 2

Conference

2:30 PM — 4:00 PM EDT

Local

May 12 Wed, 1:30 PM — 3:00 PM CDT

Aion: A Bandwidth Optimized Scheduler with AoI Guarantee

Qingyu Liu, Chengzhang Li, Thomas Hou and Wenjing Lou (Virginia Tech, USA); Sastry Kompella (Naval Research Laboratory, USA)

0

This paper investigates bandwidth minimization under AoI constraints - a fundamental problem that has not been studied in AoI research. The problem is of critical importance in bandwidth-limited IoT environment when AoI is used as a constraint. We present a novel fast algorithm called Aion that can construct a scheduler to satisfy AoI constraints with strong theoretical guarantee in terms of minimizing required bandwidth. Specifically, we prove that the bandwidth required by Aion is minimum if the AoI constraint vector meets a special mathematical structure called Fractional Consecutively Divisible (FCD). In the general case when the given AoI constraint vector is not FCD, we prove that the bandwidth required by Aion is tightly upper bounded by a factor of the minimum. The results from this paper lay the foundation for future research on bandwidth minimization with AoI guarantee.

On Scheduling with AoI Violation Tolerance

Chengzhang Li, Qingyu Liu, Shaoran Li, Yongce Chen, Thomas Hou and Wenjing Lou (Virginia Tech, USA)

0

We study an Age of Information (AoI) scheduling problem where AoI for each source at the base station (BS) can tolerate occasional violations, which we define as a violation tolerance constraint. The problem is to determine whether a set of users with given AoI deadlines, tolerance rates, and packet loss rates (due to each source's channel condition) is schedulable, and if so find a feasible scheduler. We study two cases: (i) the stable tolerant case where the tolerance rate is higher than the packet loss rate for all sources; (ii) the unstable tolerant case where the tolerance rate is lower than the packet loss rate for at least one source. For stable tolerant case, we design an algorithm called stable tolerant scheduler (STS), which can find a feasible scheduler for any network when system load is no greater than ln 2. For unstable tolerance case, we develop unstable tolerant scheduler (UTS) and identify a schedulability condition for it. Through extensive simulations, we show that STS and UTS match our theoretical results.

A Sum-of-Ratios Multi-Dimensional-Knapsack Decomposition for DNN Resource Scheduling

Menglu Yu (Iowa State University, USA); Chuan Wu (The University of Hong Kong, Hong Kong); Bo Ji (Virginia Tech, USA); Jia Liu (The Ohio State University, USA)

1

In recent years, to sustain the resource-intensive computational needs for training deep neural networks (DNNs), it is widely accepted that exploiting the parallelism in large-scale computing clusters is critical for the efficient deployments of DNN training jobs. However, existing resource schedulers for traditional computing clusters are not well suited for DNN training, which results in unsatisfactory job completion time performance. The limitations of these resource scheduling schemes motivate us to propose a new computing cluster resource scheduling framework that is able to leverage the special layered structure of DNN jobs and significantly improve their job completion times. Our contributions in this paper are three-fold: i) We develop a new resource scheduling analytical model by considering DNN's layered structure, which enables us to analytically formulate the resource scheduling optimization problem for DNN training in computing clusters; ii) Based on the proposed performance analytical model, we then develop an efficient resource scheduling algorithm based on the widely adopted parameter-server architecture using a sum-of-ratios multi-dimensional-knapsack decomposition (SMD) method to offer strong performance guarantee; iii) We conduct extensive numerical experiments to demonstrate the effectiveness of the proposed schedule algorithm and its superior performance over the state of the art.

Optimal Multicast Scheduling for Millimeter Wave Networks Leveraging Directionality and Reflections

In Sop Cho and Seung Jun Baek (Korea University, Korea (South))

0

We investigate the minimum-delay multicast problem for millimeter wave (mmWave) networks. Salient characteristics of mmWave links, directionality and reflections, are considered under sectored antenna model. We first consider directionality only, and identify the property such that the optimal policy can be recursively partitioned into smaller sizes. Using such optimal substructure, we propose an iterative method based on graphs which finds the optimal schedule in polynomial time. Next, we extend our model to incorporate reflections. We introduce the concept of path diversity which states that the availability of reflected paths enables opportunistic reduction of multicast delay. We prove NP-hardness of the problem, and propose approximations with performance bounds and heuristics of reduced complexity. By simulation we show the outperformance of our method over conventional ones, and numerically characterize the gain of path diversity in terms of network size.

Session Chair

Jie Wu (Temple University)

Session F-6

Caching 1

Conference

4:30 PM — 6:00 PM EDT

Local

May 12 Wed, 3:30 PM — 5:00 PM CDT

Cocktail Edge Caching: Ride Dynamic Trends of Content Popularity with Ensemble Learning

Tongyu Zong, Chen Li, Yuanyuan Lei and Guangyu Li (New York University, USA); Houwei Cao (New York Institute of Technology, USA); Yong Liu (New York University, USA)

2

Edge caching will play a critical role in facilitating the emerging content-rich applications. However, it faces many new challenges, in particular, the highly dynamic content popularity and the heterogeneous caching configurations. In this paper, we propose Cocktail Edge Caching, that tackles the dynamic popularity and heterogeneity through ensemble learning. Instead of trying to find a single dominating caching policy for all the caching scenarios, we employ an ensemble of constituent caching policies and adaptively select the best-performing policy to control the cache. Towards this goal, we first show through formal analysis and experiments that different variations of the LFU and LRU polices have complementary performance in different caching scenarios. We further develop a novel caching algorithm that enhances LFU/LRU with deep recurrent neural network (LSTM) based time-series analysis. Finally, we develop a deep reinforcement learning agent that adaptively combines base caching policies according to their virtual hit ratios on parallel virtual caches. Through extensive experiments driven by real content requests from two large video streaming platforms, we demonstrate that CEC not only consistently outperforms all single policies, but also improves the robustness of them. CEC can be well generalized to different caching scenarios with low computation overheads for deployment.

Cost-Driven Data Caching in the Cloud: An Algorithmic Approach

Yang Wang (Shenzhen Institute of Advanced Technology, China); Yong Zhang (SIAT, CAS, China); Xinxin Han and Pengfei Wang (Shenzhen Institutes of Advanced Technology, China); Cheng-Zhong Xu (University of Macau, China); Joseph Horton (University of New Brunswick, Canada); Joseph Culberson (University of Alberta, Canada)

1

Data caching in the cloud is an efficient way to improve the QoS of diverse data applications. However, this benefit is not freely available, given monetary cost to manage the caches in the cloud. In this paper, we study the data caching problem in the cloud that is driven by the monetary cost reduction, instead of the hit rate under limited capacity as in traditional cases. In particular, given a stream of requests R to a shared data item, we present a shortest-path based optimal algorithm that can minimize the total transfer and caching costs within O(mn) time for off-line case, here m represents the number of nodes in the network, while n is the length of the request stream. The cost model in this computation is semi-homo, which indicates that all pairs of nodes have the same transfer cost, but each cache server node has its own caching cost rate. Our off-line algorithm improves the previous results not only in reducing the time complexity from O(m 2 n) to O(mn), but also in relaxing the cost model to be semi-homogeneous, rendering the algorithm more practical in reality. Furthermore, we also study this problem in its online form, and by extending the anticipatory caching idea, we propose a 2-competitive online algorithm based on the same cost model and show its tightness by giving a lower bound of the competitive ratio as 2 − o(1) for any deterministic online algorithm. We provably achieve these results with our deep insights into the problem and careful analysis of the solution algorithms, together with a trace-based study to evaluate their performance in reality.

Fresh Caching for Dynamic Content

Bahman Abolhassani (The Ohio State University, USA); John Tadrous (Gonzaga University, USA); Atilla Eryilmaz (The Ohio State University, USA); Edmund Yeh (Northeastern University, USA)

3

We introduce a framework and provably-efficient schemes for 'fresh' caching at the (front-end) local cache of content that is subject to 'dynamic' updates at the (back-end) database. We start by formulating the hard-cache-constrained problem for this setting, which quickly becomes intractable due to the limited cache. To bypass this challenge, we first propose a flexible time-based-eviction model to derive the average system cost function that measures the system's cost due to the service of aging content in addition to the regular cache miss cost. Next, we solve the cache-unconstrained case, which reveals how the refresh dynamics and popularity of content affect the optimal caching. Then, we extend our approach to a soft-cache-constrained version, where we can guarantee that the cache use is limited with arbitrarily high probability. The corresponding solution reveals the interesting insight that 'whether to cache an item or not in the local cache?' depends primarily on its popularity level, whereas 'how long the cached item should be held in the cache before eviction?' depends primarily on its refresh rate. Moreover, we investigate the cost-cache saving tradeoffs and prove that substantial cache gains can be obtained while also asymptotically achieving the minimum cost as the database size grows.

GRADES: Gradient Descent for Similarity Caching

Anirudh Sabnis (University of Massachusetts Amherst, USA); Tareq Si Salem and Giovanni Neglia (Inria, France); Michele Garetto (Università di Torino, Italy); Emilio Leonardi (Politecnico di Torino, Italy); Ramesh K Sitaraman (University of Massachusetts, Amherst & Akamai Technologies, USA)

2

A similarity cache can reply to a query for an object with similar objects stored locally. In some applications of similarity caches, queries and objects are naturally represented as points in a continuous space. Examples include 360 ◦ videos where user's head orientation-expressed in spherical coordinates- determines what part of the video needs to be retrieved, and recommendation systems where the objects are embedded in a finite-dimensional space with a distance metric to capture content dissimilarity. Existing similarity caching policies are simple modifications of classic policies like LRU, LFU, and qLRU and ignore the continuous nature of the space where objects are embedded. In this paper, we propose GRADES, a new similarity caching policy that uses gradient descent to navigate the continuous space and find the optimal objects to store in the cache. We provide theoretical convergence guarantees and show GRADES increases the similarity of the objects served by the cache in both applications mentioned above.

Session Chair

Marie-Jose Montpetit (Concordia University, Canada)

Program at a Glance